package com.leetcode.problems044;

/**
 * https://leetcode-cn.com/problems/wildcard-matching/
 * @Date 2021/12/09 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    public boolean isMatch(String s, String p) {
        if(s.length() == 0 && p.length() == 0){
            return true;
        }
        if(s.length() !=0 && p.length() == 0){
            return false;
        }
        if(s.length() == 0){
            return noMoreMatch(p, 0);
        }
        int[][] memo = new int[s.length()][p.length()];
        return match(s,p,0,0,memo);
    }

    public boolean match(String s, String p,int si,int pi,int[][] memo){
        if(si == s.length()){
            return noMoreMatch(p, pi);
        }

        if(pi == p.length()){
            return false;
        }

        if(memo[si][pi] != 0){
            return memo[si][pi] == 1;
        }

        if(p.charAt(pi) == '*'){
            if( match(s,p,si + 1,pi,memo) || match(s,p,si,pi+1,memo)){
                memo[si][pi] = 1;
            }else{
                memo[si][pi] = -1;
            }
        }else{
            if(isSample(s.charAt(si),p.charAt(pi))){
                if(match(s,p,si + 1,pi + 1,memo)){
                    memo[si][pi] = 1;
                }
            }else{
                memo[si][pi] = -1;
            }
        }
        return memo[si][pi] == 1;
    }

    private boolean noMoreMatch(String p, int pi) {
        for (int i = pi; i < p.length(); i++) {
            if (p.charAt(i) != '*') {
                return false;
            }
        }
        return true;
    }

    private boolean isSample(char sc,char pc){
        return sc == pc || pc == '?';
    }

    public static void main(String[] args) {
        String s = "aa";
        String p = "a?";
        System.out.println(new Solution().isMatch(s,p));
    }
}
